﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Chapter_9__Recursion_
{
    public static class Ex_9_5
    {
        static bool UseDynamicProgramming = true;

        public static SortedSet<string> GetAllPermutations(string InString)
        {
            if (InString == null || InString.Length < 2)
            {
                SortedSet<string> newList = new SortedSet<string>();
                newList.Add(InString);
                return newList;
            }

            Char lastChar = InString[0];
            SortedSet<string> Permutations = GetAllPermutations(InString.Substring(1));
            SortedSet<string> newPermutations = new SortedSet<string>();
            foreach (string permutation in Permutations)
            {
                for (int i = 0; i <= permutation.Length; i++)
                {
                    newPermutations.Add(permutation.Insert(i, lastChar.ToString()));
                }
            }

            return newPermutations;
        }

        
    }
}
